1. Field of the Invention
The present invention relates to a path retrieving circuit operated to decide a device to which a packet is to be transferred based on information about a destination address to specify a receiving unit of the packet, a communication control unit such as a router employing the above path retrieving circuit or a like and more particularly to the path retrieving circuit required to solve a problem of conformity between an IP (Internet Protocol) address being used in the Internet and a network address defined by an address and a mask strength and the communication control unit using the above path retrieving circuit.
2. Description of the Related Art
Communication control units such as a bridge or a router used to pass on packet data between two or more networks, for example, between LANs (Local Area Network) are well known. The bridge establishes a connection at a level of a data link layer in a reference model of an OSI (Open Systems Interconnection) designated by ISO (International Organization for Standard). Moreover, the router establishes a connection at a level of a network layer being an upper layer of the data link layer.
Conventionally, path table information is preliminarily set in the communication control unit such as bridges, routers or a like. The communication control unit, when receiving packet data through the network, is operated to judge a place to which the received packet data is to be transferred in accordance with the path table information. In this processing of the judgement, in general, a path table is retrieved based on an address stored in an address field of the received packet data and to which device the received packet data is to be transferred is then judged.
Next, an example of the retrieving using an address employed in the LAN will be explained below briefly.
The address used in the LAN includes an MAC (Medium Access Control) address on an ethernet network, an address specific to a unit such as an ATM (Asynchronous Transfer Mode) device in an ATM network, a network number used among these communication devices, a network address representing a unit number on the network or a like.
The sending and receiving data transmitted at a level of the network layer in the LAN ordinarily includes an internet work address to identify a destination address and source address. An IP address (32 bits) in a TCP/IP (Transmission Control Protocol/Internet Protocol) is well known as the internet work address.
The router is operated, by referencing to a destination IP address of the received packet, to judge to which router or terminal the received packet is to be transmitted in the processing of the judgement, after having judged to which network address the destination IP address of the received packet belongs and to decide a physical address of the destination address corresponding to the network address.
The network address is defined by the IP address and a mask length. The mask length is information showing up to which bit from a high order bit is valid as the network address in the IP address.
An example of the network address is shown in FIG. 30. In the example in FIG. 30, since the mask length is 16 bits, high order 16 bits out of the IP address [800A0000] are valid as the network address. If the mask length is xe2x80x9c16xe2x80x9d, the mask address is defined as [FFFF0000] with the high order 16 bits representing xe2x80x9c1xe2x80x9d and with low order 16 bits representing xe2x80x9c0xe2x80x9d. When a result obtained by ANDing the destination IP address of the received packet and the above mask address conforms to the IP address [600A0000], the destination IP address is judged to have conformed to the network address.
For example, if the destination IP address is [800A40C8], a result obtaining by ANDing the destination IP address [800A40C8] and the mask address [FFFF0000] is [800A0000] . This conforms to the IP address [800A0000]. Therefore, the destination IP address is judged to conform to the network address.
Conventionally, the conformity between the destination IP address and the network address has seen solved simply by using a concept of a xe2x80x9cClassxe2x80x9d. That is, if the high order bit of the IP address is xe2x80x9c0xe2x80x9d, the address fits into the xe2x80x9cClass Axe2x80x9d having its mask length being 8 bits, if the high order bit of the IP address is xe2x80x9c10xe2x80x9d, the address fits into the xe2x80x9cClass Bxe2x80x9d having its mask length being 16 bits and if the high order bit of the IP address is xe2x80x9c100xe2x80x9d, the address fits into the xe2x80x9cClass Cxe2x80x9d having its mask length being 24 bits.
However, in recent years, due to a widespread use of subnet or CIDR (Classless Internet Domain Routing), the concept of the xe2x80x9cClassxe2x80x9d s not used. This does not allow the network address to be simply judged from the IP address, causing much time required to judge the network address.
Moreover, in some networks employing the CIDR, there are cases in which a plurality of network addresses conforming to the destination IP address may exist in the path table. In this case, path information given by the network address having the largest mask length is employed.
As described above, the conventional communication control units including the bridge, router or like have a problem in that, when the packet data is transferred on the network having much path information, much time is required to process the path information.
Especially, in the case of transferring the packet data on the network having a plurality of network addresses matching to a specified destination address, since an algorithm for solving contents of the network address is made complicated and further much time is required to process the path information. This causes a reduction in throughput of packet transferring processing in the packet transferring unit.
In the conventional router used in the Internet, a path deciding processing for determining a device to which the packet data is to be transferred next, based on the destination IP address, is implemented by using software; that is to say, the path information to be retrieved out of much path information is implemented by the software.
The inventor of the present invention has disclosed a technology capable of reducing the time required for the path solving processing in Japanese Patent Application No. Hei9-356774. As shown in FIG. 32, disclosed technology is excellent in that the path solving processing can be performed at a high speed by implementing the retrieval algorithm composed of a binary tree structure (path tree or RT0) using a hardware circuit. Details of the path tree shown in FIG. 32 are described later.
Hereafter, technology disclosed in the Japanese Patent Application No. Hei9-356774 will be described in detail.
FIG. 31 is a schematic block diagram showing configurations of a conventional communication control unit. As shown in FIG. 31, the conventional communication control unit is composed of an input/output device 1, a path retrieving circuit 2a and a path tree storing memory 3.
The input/output device 1 is a device to perform processing of a received packet, which requests the path retrieving circuit 2a to perform path information retrieving and judges a destination address of the received packet based on a result R of path information retrieving (hereinafter maybe referred to as result of retrieving) outputted from the path retrieving circuit 2a as a result of the requested retrieval.
The path retrieving circuit 2a, when receiving a retrieval requesting signal S and a destination IP address A from the input/output device 1, is operated to retrieve the path information corresponding to the destination IP address by using the path tree storing memory 3 and then to output a retrieval completion signal E and result R of retrieving to the input/output device 1.
A path table shown as Table 1 which corresponds to the path tree, as shown in FIG. 32, used for determining the place to which the packet is to be transferred is stored in the path tree storing memory 3.
Next, the path tree shown in FIG. 32 is described below. As shown in FIG. 32, the path tree is composed of a path node (nod 1) and a transit node (nod 2). Each path node (nod 1) has a path entry corresponding to each place to be transferred to. The transit node (nod 2) does not have the path entry and is provided as a branch node used to establish a connection among path nodes (nod 1). A number given at an upper stage in a block of each node represents a node number N. A number given at the front of a slash [/] out of lumbers at a lower stage in a block represents an IP address (real address) and a number at the rear of the slash [/] represents a mask length (real mask length).
Thus, the path tree corresponding to the path table is so configured that an unnecessary branch is removed in order to achieve high speed retrieving. As depicted in Table 1 and FIG. 32, the node of the path tree has larger mask lengths at its farther ends of the tree structure. Because of this, the mask length of the node becomes larger as the node is read later.
FIG. 33 is a schematic block diagram showing configurations or the conventional path retrieving circuit 2a. As shown in FIG. 33, the path retrieving circuit 2a is chiefly includes a state managing circuit 1023, a next node selecting circuit 1020 which performs retrieving processing for every node, a path renewing circuit 1021 and a retrieving end judging circuit 1022.
The next node selecting circuit 1020 is provided with a decoding circuit (not shown) to select one bit and, when retrieving the path, is operated to extract one bit of the retrieving IP address from the mask information in a cycle of one clock and then to select to which node, a left child node or a right child node of the tree structure, the path should be branched. This allows one entry processing (one node processing) to be implemented in the cycle of one clock. At this point, the processing of selecting one bit of the address to decide the branching to a next node and processing of comparing the address with the network address held by the node are performed on all bits of the address.
Moreover, the path renewing circuit 1021 has an address comparing circuit (not shown) which performs a comparison between the IP network address designated by the mask length cut of IP addresses of the read node and the retrieving IP address. When the results from the comparison conform to each other, the path information of the read node is held. The comparison between the retrieving IP address and the network address held by the node is made for all bit widths.
The retrieving end judging circuit 1022 judges the retrieving processing to be terminated when the rode to be next read by the next node selecting circuit 1020 does not exist or when the results from the comparison do not conform to each other. Immediately when retrieving is judged to be terminated, the path information held lastly by the path renewing circuit 1021 becomes path information that can correspond to the retrieving IP address. The information about termination of the retrieving is notified to the input/output device 1.
The technology disclosed in Japanese Patent Application No. Hei9-356774 is excellent in that time required for processing of determining the path is shortened because the path retrieving is implemented by the hardware circuit not by algorithm.
However, though the path retrieving is implemented by the hardware circuit, it still has points to be technologically improved. In the conventional path retrieving, since the length of an address to be retrieved is predetermined, it is impossible to retrieve the address if its length is greater than the predetermined one. In the conventional technology, in order to retrieve very long address, the decoding circuit to select the bit and the address comparing circuit have to be made large-scaled so that they can treat big bit numbers.
Moreover, whenever processing for every entry is performed, processing of comparing by the number of bits of the address is required. Because of this, if the address to be retrieved is long, much time is required to retrieve each entry. As a result, when one entry is retrieved in a cycle of one clock, if the number of bits of the address to be retrieved increases, since it is difficult to shorten the clock cycle and an operational clock frequency has to be lowered, the processing speed is lowered accordingly.
When the hardware circuit being capable of retrieving the very long address is fabricated, it is necessary to express each node of the path tree by using a long address. This causes an increase in capacity of the memory required to store the retrieving table corresponding to the path tree.
In view of the above, it is an object of the present invention to provide a communication control unit which is capable of retrieving a destination regardless of length of an address to be retrieved, of reducing a size of a circuit of the communication control unit, of achieving a high speed processing of retrieval and of preventing an increase in a memory capacity.
According to a aspect of the present invention, there is provided a communication control unit including:
a memory device storing a path table corresponding to a path tree used to retrieve a place to which received packet data is transferred, wherein a node constituting the path tree is represented by a split address containing a least significant bit of a valid address of a real address out of each of the split addresses obtained by setting off the real address of the node by every specified bit starting from its high order portion and by a split mask length showing a count of bits of a valid address portion of the real address;
a path retrieving circuit including a retrieval data managing circuit, a next node selecting circuit and a path renewing circuit, wherein the retrieval data managing circuit is operated to produce a split retrieving address including two or more stages obtained by setting off the retrieving address showing a destination for received packet data by every specified bit and, at a same time, to generate a bit string for selection including a bit string obtained by displacing the bit string of the split retrieving address by one bit toward a low order portion on the retrieving address, wherein the next node selecting circuit is operated to decide the node to be next retrieved based on the bit having a value being equivalent to a value of a length of high order split mask contained in the bit strings for selection and wherein the path renewing circuit is operated to compare a valid address portion being equivalent to the count of bits represented by the length of the high order split mask contained in split addresses showing the node decided by the next node selecting circuit with the bit string being equivalent to the count of bits represented by the length of the high order split mask contained in split retrieving addresses outputted from the retrieval data managing circuit and if comparison results conform to each other, to hold path information corresponding to the node and to output path information being held at a time of termination of the retrieving processing as a place to which the received packet data is to be transferred.
By configuring as above, each node of the path tree is represented by the split address, split mask length and the address to be retrieved is also split, the split retrieving address is produced and the split bit strings are sequentially compared with each other. Therefore, the place to which the packet is transferred can be retrieved regardless of the length of the address to be retrieved, that is, the retrieving address may be a variable-length address. Moreover, a memory capacity required to store data of the node can be reduced more when compared with a case wherein each node is represented by the real address or real mask length. Even when the address entered is long, since the split address is stored as data of the node, an increase in memory capacity can be avoided. Furthermore, the processing of retrieving the node is performed by splitting the retrieving address. This allows each node to be retrieved depending on a scale or a circuit corresponding to the count of bits of the split retrieving address. Therefore, configurations of the circuit can be made smaller in scale when compared with the case where the node is retrieved based on the real address or real mask length. Even if the retrieving address is long, each node can be retrieved depending on scale of the circuit corresponding to the count of bits of the split retrieving address. This can prevent an increase in the scale of configurations of the circuit. Since the node represented by the split address and split mask length is retrieved based on the split retrieving address, the count of bits to be retrieved for each node can be reduced more when compared with the case in which the retrieving is performed based on the actual retrieving address, thus allowing high speed retrieving of the node. Also, since the count of bits of each node to be retrieved can still remain the court of bits of the split retrieving address, even when the retrieving address is long, time required to retrieve each node can be shortened, thus allowing high speed retrieving.
In the foregoing, a preferable mode is one that the path tree corresponding to the path table stored in the memory device has the node with its split mask length being equivalent to the specified count of bits on the path establishing the connection. among nodes represented by different split bit strings and wherein the retrieval data managing section, when the node to be compared in the path renewing circuit is renewed from the node with the split mask length being equivalent to the specified number of bits to the next node, is operated to update the split retrieving address and the bit string for selection to be outputted to the path renewing circuit so as to exist at a next stage.
By configuring as above, since the split retrieving address is updated every time the split mask length becomes a specified count of bits, when the split address showing the node and the split retrieving address serving as a retrieve key are referenced to, the split address and split retrieving address can be compared surely between bit strings corresponding to each other.
Also, a preferable mode is one wherein the node includes a path node corresponding to path information showing the place to which the packet data is to be transferred, a transit node not corresponding to path information, having the split mask length being equivalent to a value being less than the specified number of bits and serving as a branch point between two nodes and a boundary node not corresponding to path information, having the split mask length being equivalent to the specified number of bits and not serving as the branch point.
By configuring above, since the path tree includes three kinds of boundary nodes including the path node, transit node and boundary node, efficient retrieving of the path can be achieved by using minimum necessary number of nodes.
Also, a preferable mode is one that wherein includes a mask length comparing circuit operated to compare the real mask length showing the valid address of the retrieving address and the count of bits of the valid address of the real address of the node to be retrieved.
By configuring as above, a state that the valid address of the retrieving address serving as a reference or judgement of termination of the retrieving becomes longer than the valid address of the real address of the node to be retrieved can be easily detected.
Also, a preferable mode is one that wherein includes a retrieval end identifying circuit operated to judge the retrieving to be terminated when there is no next node to be selected in the next node selecting circuit, when comparison results do not conform to each other in the path renewing circuit or when the valid address of the retrieving address is longer than the valid address of the real address of the node to be retrieved.
By configuring as above, the termination of retrieving can be easily judged.
Also, a preferable mode is one wherein the next node selecting circuit includes a first selector operated to select the bit represented by the split mask length out of the specified number of bits and a second selector operated to select one node as the next node out of maximum two nodes based on a value of the bit selected by the first selector.
By configuring as above, when the retrieval processing is implemented by hardware, the count of bits such as the register, decoder or a like constituting the first selector can be limited to the count of bits of the split address or split mask length. This allows a reduction of the circuit scale even in the case of long retrieving address.
Also, a preferable mode is one wherein the path renewing circuit includes a mask processing circuit into which the split mask length of the split address showing the node decided by the next node selecting circuit and the split retrieving address are inputted and which is operated to extract the bit string being equivalent to the count of bits represented by the split mask length from the high order portion of the split retrieving address, an address comparing circuit operated to compare the extracted bit string with the valid address portion being equivalent to the count of bits represented by the split mask length out of the high order portion of the split address and a path information renewing circuit operated to hold path information corresponding to the node if the comparison results conform to each other and to output path information held at time of termination of the retrieving as the place to which the received packet data is to be transferred.
By configuring as above, the retrieval processing can be implemented by circuits corresponding to the count of bits of the split retrieving address or split mask length, thus preventing increase in circuit configurations even if the retrieving address is long.
Also, a preferable mode is one that wherein includes an entry adding circuit operated to add the node of an additional entry to the place retrieved as an additional position by the path retrieving circuit in the path tree.
Furthermore, a preferable mode is one that wherein includes an entry deleting circuit operated to delete the node corresponding to the place retrieved as a deletion position by the path retrieving circuit in the path tree.